הבניין נבנה בשנת 1874 ע"י משפחת שטרן, משפחת תעשיינים ציונית שעלתה מגרמניה. המגורים בירושלים שבין חומות העיר העתיקה היו צפופים מדי למשפחה האמידה, והיות והיו אלה ימי היציאה מן החומות רכש מקס מרדכי שטרן מן הכנסייה היוונית אורתודוקסית שטח אדמה באזור ממילא במרחק הליכה מבתי הכנסת בתוך החומות, ועליו הקים בית מרווח ומפואר בסטנדרט אירופאי.
ב 28 לאוקטובר 1898 הגיע הקיסר וילהלם השני לביקור בירושלים לרגל חנוכת כנסיית הגואל הסמוכה לכנסיית הקבר.
פמלייתו של הקיסר מנתה כ-200 איש, שמילאו לחלוטין את מעט בתי המלון בירושלים והחדר שהוזמן עבור בנימין זאב הרצל, הועבר לשימוש פמליית הקיסר. הרצל הגיע מיפו לירושלים באתו יום, יום שישי, מיפו ברכבת מיוחדת שהוספה ללוח הזמנים הרגיל. כנראה שבעלי מלון קמינץ לא היו מודעים לרכבת הנוספת, ומאחר והרצל ופמלייתו לא הגיעו ברכבת האחרונה מסרו את החדרים לאורחים אחרים.
כשהגיע הרצל ברכבת, היה חולה ומותש מהדרך אך הוא סרב לנסוע בעגלה למלון שלא לחלל שבת, כשהגיע למלון התבשר כי חדרו נמסר לאחר ולאחר דין ודברים קיבלו הרצל ופמלייתו שני חדרים קטנים, באחד לן הרצל ודר' משה שנירר חבר במשלחת ובחדר השני שלושה חברים נוספים. למחרת, יום שבת ביקש הרצל למצוא אכסניה אחרת בגלל חוסר הנוחות וגם משום שהמלון היה מאוכלס בקצינים תורכים דוברי גרמנית דבר שהקשה על חברי המשלחת לנהל שיחות בפרטיות. מקס מרדכי שטרן קיבל על עצמו לארח את המנהיג הציוני בביתו המרווח, אשר הפך בסיס לאותו ביקור של הרצל בעיר, שבמהלכו נפגש עם הקיסר לפגישה קצרה ומאכזבת מבחינת תרומתה לרעיון הציוני. ארבעה לילות לן הרצל בבית שטרן. מאוחר יותר הפכה משפחת שטרן את החדר בביתם שבו לן הרצל למוזיאון קטן מוזיאון "חדר הרצל" פעל בבניין עד שבשנות ה-70 נתקבלה ההחלטה על פיתוח הרובע תוך הריסתו ותכנונו מחדש על פי תוכניתו של האדריכל משה ספדיה. בית שטרן היה מן המבנים שיועדו להריסה. התנגדות עזה מצד משפחת שטרן, תמיכה ציבורית של תושבים ושל המועצה לשימור אתרים, הצליחה לסכל את תוכנית ההריסה של בניין זה, ונקבע כי הבית ישומר וישולב בין המבנים החדשים שנועדו להיבנות במקום. הבניין פורק ואבניו מוספרו, סומנו והועברו לאחסון. בשנת 2006, אחרי ההתדיינות המשפטית ארוכת השנים (שנגעה בין היתר למלחמות השבת בירושלים, והמאבק על צביונו של המיזם) , חודשו העבודות. עם חידוש העבודות ניגשו היזמים להקמתו מחדש של בית שטרן על פי התוכנית, דבר שנתברר כקשה מהצפוי עקב הזמן הרב שחלף מאז הפירוק, אובדן רישומים וחוסר התאמה בין התוכניות לבין האבנים שפורקו. עבודות שחזור מעטפת האבן החיצונית של בית שטרן בוצעו על ידי מומחי שחזור והסתיימו רק בנובמבר 2007. הבניין המשוחזר רחוק מלהיות זהה למבנה המקורי וזאת בעיקר בגלל שילובו בתכנון האדריכלי של "רובע אלרוב ממילא". החלק הדרום מערבי של המבנה , שהיה מטויח במקורו, הפך להיות מחופה אבן ואילו החזית הצפונית של הבניין עברה שינוי מבני כדי להתאים את עצמה לרחוב ממילא, שהפך ממשופע למישורי. בחזית הפונה דרומה נבנתה מרפסת אבן חדשה, שבה מתוכננת הצבת פסל בדמותו של הרצל על המרפסת בבזל. הבניין מאכלס את חנות הדגל של רשת חנויות הספרים סטימצקי. לבקשת המועצה להנצחת מורשת הרצל והמועצה לשימור אתרים הסכימה הנהלת רשת סטימצקי להקדיש חלק ממבנה החנות למיצג על הרצל ותולדות המבנה, וכן לכלול בחנות אגף מיוחד לספרים על הרצל והציונות. הפינה המוקדשת להרצל נמצאת במרתף הבניין, סמוך לשירותים והיא חובבנית ועלובה ולא מביאה כבוד רב לחוזה המדינה וחברת סטימצקי שבחסותה התצוגה הדלה.
